% This is a sample LaTeX input file.  (Version of 9 April 1986)
%
% A '%' character causes TeX to ignore all remaining text on the line,
% and is used for comments like this one.
\documentclass[11pt]{article}    % Specifies the document style.
\usepackage[pdftex]{graphicx}
\usepackage{setspace} % Import setspace package
\usepackage{url}
\usepackage{grffile}
\usepackage{xskak}
\usepackage{fancyvrb}
\usepackage{listings}
\usepackage{tikz}
\usepackage[bottom]{footmisc}
\usepackage{amsmath,amsthm,amssymb,stmaryrd,mathabx}

\bibliographystyle{alpha}

\linespread{1.6} %Set the iine spacing
								% The preamble begins here.
\usepackage[retainorgcmds]{IEEEtrantools}


\title{Towards a Thesis:)}  % Declares the document's title.
\author{Andreas Bok Andersen \url{aboa@itu.dk}}
\begin{document}           % End of preamble and beginning of text.
\maketitle                 % Produces the title
\thispagestyle{empty}
\pagebreak
\section{The problem}
Detection of protein families in large databases is one of the principal research objectives in structural and functional genomics. Protein family classification can significantly contribute to the delineation of functional diversity of homologous proteins, the prediction of function based on domain architecture or the presence of sequence motifs as well as comparative genomics, providing valuable evolutionary insights.\footnote{Ouzounis et al (2002) - An efficient algorithm for large-scale detection of protein families}

Several algorithms exist to cluster protein sequences into families. The JClust library \footnote{\url{http://jclust.embl.de/}} thus implements k-Means, Affinity Propagation, Spectral Clustering, Markov Clustering (MCL), Restricted Neighborhood Search Cluster (RNSC). Especially Markov Clustering (MCL) has been used succesfully. It relies on the assignment of proteins into families based on precomputed sequence similarity information and provides accurate detection of protein families on a large scale. The method has been used to detect and categorise protein families within the draft human genome and the resulting families have been used to annotate a large proportion of human proteins. 

\section{Markov Clustering - A brief overview}\footnote{\url{http://jclust.embl.de/algorithms.html}}
The MCL algorithm is a fast and scalable unsupervised clustering algorithm based on simulation of stochastic flow in graphs. The process deterministically computes the probabilities of random walks through a graph, and uses two operators transforming one set of probabilities into another. It does so by using the language of stochastic matrices (also called Markov matrices) which capture the mathematical concept of random walks on a graph. 

The basic idea underlying the MCL algorithm is that dense regions in sparse graphs correspond with regions in which the number of k-length paths is relatively large, for small k in N, which corresponds to multiplying probabilities in the matrix appropriately. Random walks of length k have higher probability (product) for paths with beginning and ending in the same dense region than for other paths.

The algorithm starts by creating a Markov matrix from the graph, where first, in the adjacency matrix, diagonal elements are added to include self-loops for all nodes, i.e., probabilities that the random walker stays at a particular node. After this initialisation, the algorithm works by alternating two operations, expansion and inflation, iteratively recomputing the set of transition probabilities. The expansion step corresponds to matrix multiplication (on stochastic matrices), the inflation step corresponds with a parametrized inflation operator $Gamma_r$, which acts column-wise on (column) stochastic matrices (here, we use row-wise operation, which is analogous).
 
The inflation operator transforms a stochastic matrix into another one by raising each element to a positive power p and re-normalising columns to keep the matrix stochastic. The effect is that larger probabilities in each column are emphasized and smaller ones deemphasized. On the other side, the matrix multiplication in the expansion step creates new non-zero elements, i.e., edges. The algorithm converges very fast, and the result is an idempotent Markov matrix, $M = M * M$, which represents a hard clustering of the graph into components.
 
Expansion and inflation have two opposing effects: While expansion flattens the stochastic distributions in the columns and thus causes paths of a random walker to become more evenly spread, inflation contracts them to favoured paths.\footnote{The mathematical basis of the MCL algorithm is the subject of Stijn van Dongen's thesis Graph Clustering by Flow Simluation \url{ http://micans.org/mcl/index.html?sec_thesisetc}}

\begin{figure}
	\centering
		\includegraphics[width=1.00\textwidth]{C:/Users/Andreas/Documents/ITU/Thesis/flowchart_tribe-mcl.jpg}
		\caption{Flowchart of the MCL algorithm}
	\label{fig:flowchart_tribe-mcl}
\end{figure}
\subsection{Computational aspects and challenges}
The timecomplexity is $O(Nk^2)$ where n is the number of the nodes, k the number of centers. 
The space complexity is of order $O(N^2)$. 
The bounds are feasible in practice for small input sizes. But clustering $protein-sequences$ which involve ie. larger subsets of the human genes (in total $20000-25000$) mapped by the Human Genome Project\footnote{\url{http://www.ornl.gov/sci/techresources/Human_Genome/home.shtml}} renders the computation intractable in with regard to space complexity and I/O operations needed for the matrix multiplication, the adjacency not fitting in RAM.
Presently the techniques to optimization of time, $space/memory$ load lies in the pruning of intermediary MCL iterations. \\
What I intend to investigate is whether a cache oblivious strategy could be adopted and thus lead to a higher upper bound for the size of the input. 
Another topic could be the parallelization of the algorithm as multithreading is already integrated in the present implementation. 




\end{document}
% End of document